package leetcode.code0767;

import java.util.PriorityQueue;

public class Solution1 {
	public String reorganizeString(String s) {
		char[] cs = s.toCharArray();
		int len = cs.length;
		int[] hash = new int[128];
		int max = 0;
		for (int i = 0; i < len; i++) {
			max = Math.max(max, ++hash[cs[i]]);
		}
		if (max > (len + 1) >> 1) {
			return "";
		}
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
		for (int i = 0, num = 0; i < hash.length; i++) {
			if ((num = hash[i]) != 0) {
				queue.add(new int[] { num, i });
			}
		}
		char[] ans = new char[len];
		int[] cur = queue.poll();
		int p = 0;
		ans[p++] = (char) cur[1];
		cur[0]--;
		while (!queue.isEmpty()) {
			int[] add = queue.poll();
			ans[p++] = (char) add[1];
			add[0]--;
			if (cur[0] != 0)
				queue.add(cur);
			cur = add;
		}
		return new String(ans);
	}
}
